public class PalindromeLinkedList {
    // 链表节点定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { 
            val = x; 
            next = null; 
        }
    }

    // 主方法：判断链表是否为回文结构
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        // 找到中点（使用快慢指针）
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 反转后半部分链表
        ListNode secondHalf = reverseList(slow.next);
        ListNode p1 = head;
        ListNode p2 = secondHalf;
        
        // 比较前半部分和反转后的后半部分
        boolean result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        
        // 可选：恢复原链表结构（此处未实现）
        return result;
    }

    // 辅助方法：反转链表
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // 测试用例
    public static void main(String[] args) {
        PalindromeLinkedList solution = new PalindromeLinkedList();
        
        // 测试回文链表 1->2->2->1
        ListNode palindrome = new ListNode(1);
        palindrome.next = new ListNode(2);
        palindrome.next.next = new ListNode(2);
        palindrome.next.next.next = new ListNode(1);
        System.out.println("是否为回文: " + solution.isPalindrome(palindrome)); // 输出 true
        
        // 测试非回文链表 1->2->3
        ListNode notPalindrome = new ListNode(1);
        notPalindrome.next = new ListNode(2);
        notPalindrome.next.next = new ListNode(3);
        System.out.println("是否为回文: " + solution.isPalindrome(notPalindrome)); // 输出 false
        
        // 测试奇数长度回文 1->2->1
        ListNode oddPalindrome = new ListNode(1);
        oddPalindrome.next = new ListNode(2);
        oddPalindrome.next.next = new ListNode(1);
        System.out.println("是否为回文: " + solution.isPalindrome(oddPalindrome)); // 输出 true
    }
}